1. Technical Field of the Invention
The present invention provides a method and apparatus for implementing a non-blocking minimal spanning switch.
2. Background of the Invention
Telecommunication systems require switching networks to transmit data signals, or messages, from one point of the network to another point of the network. Many systems often employ the Clos Network, a type of switch network, for data transfer. The Clos Network is a multi-stage switch network, where each stage consists of a crossbar or crossbar switch. The system can be arranged into three stages: the ingress stage; the middle stage; and the egress stage. A total of n inputs are allowed into the ingress stage, where n=the total number of data input signals which are transmitted into the total crossbar connections (r) of the ingress stage (or any other stage). The data input into the ingress stage is subsequently output from the ingress stage; a total of m outputs are allowed, where m=the total number of data output signals which are transmitted out of the ingress stage and m=the total number of crossbar connections located in the middle stage. One connection is provided to allow the data from the (n−1) data inputs of the ingress stage to be transmitted out of the ingress stage and into the middle stage, and one connection is provided to allow this data to be transmitted out of the middle stage and into the egress stage. The classic Clos Network switch fabric is illustrated in FIG. 7.
Charles Clos further defines a Strict-Sense Non-Blocking Clos Network, where unused ingress crossbar connections are connected to unused egress crossbar connections, where m≧(2n−1). In a typical three stage Clos Network, to guarantee the connection of n connections, (2n−1) crossbar connections are required in the middle stage; with (n−1) data inputs active in the ingress stage crossbar connections, and another (n−1) data inputs potentially active in the egress stage crossbar connections, (2n−2) crossbar connections are required in the middle stage to allow the connection, where (n−1)+(n−1)=(2n−2). However, as (2n−2) crossbar connections may be unable to provide every necessary connection, an extra crossbar is provided to ensure Strict-Sense Non-Blocking, with (2n−1) middle stage crossbar connections.
(2n−1) middle stage crossbar connections would consume a large amount of resources, but in a Clos Network, m≧(2n−1) is necessary to maintain Strict-Sense Non-Blocking. When implementing a Clos Network which does not adhere to m≧(2n−1), the data connections may need to be re-routed in order to establish new connections, and such re-routing would result in interrupted or blocked connections, i.e., dropped telephone connections.
One method of minimizing the number of crossbar connections in the middle stage is through the use of a Non-Blocking Minimal Spanning Switch. When using a Non-Blocking Minimal Spanning Switch system, the connections between the ingress stage, middle stage and egress stage are symmetrical, with n ingress stage crossbar connections, n middle stage crossbar connections and n egress stage crossbar connections. This is achieved through the use of multiple sub-switches located in each stage; as an example a 4×4 switch including two input crossbar connections and two output crossbar connections are used. In a Non-Blocking Minimal Spanning Switch system, any data input signal input to any ingress location may be output from any egress location provided there is an open connection and an open path; however, signals can be blocked when they arrive from the ingress stage to the middle stage where the sub-switch locations are already in use, requiring other signals to be re-routed to ensure transmission. Such re-routing of signals is undesirable; the signals being transmitted are already carrying data, thus re-routing the data signal would again result in interrupted or blocked connections, i.e., dropped telephone connections.
Therefore, a method of re-routing the data signals transmitted through switching fabrics, without causing such interruptions, is required.